﻿namespace AlgLrnLib.Sorting
{
    public class MergeSort : BaseSort
    {
        #region Public Methods
        public override int[] SortAsc(int[] numbers, DebugTraceDelegate DEBUG_TRACE)
        {
            DEBUG_TRACE(numbers, "Asc Sort - Initial Load", true);

            return SplitAndMerge(DEBUG_TRACE, numbers, 0, numbers.Length - 1);
        }

        public override int[] SortDesc(int[] numbers, DebugTraceDelegate DEBUG_TRACE)
        {
            DEBUG_TRACE(numbers, "Desc Sort - Initial Load", true);

            return SplitAndMerge(DEBUG_TRACE, numbers, 0, numbers.Length - 1, false);
        }
        #endregion

        #region Private Methods
        private int[] SplitAndMerge(DebugTraceDelegate DEBUG_TRACE, int[] numbers, int nStartIdx, int nEndIdx, bool asc = true)
        {
            DUMP(numbers, nStartIdx, nEndIdx, DEBUG_TRACE, false);

            if (nStartIdx == nEndIdx) // only one element
                return numbers;

            int nMiddleIdx = (nStartIdx + nEndIdx) / 2; // same as nStartIdx + (nEndIdx - nStartIdx) / 2;

            numbers = SplitAndMerge(DEBUG_TRACE, numbers, nStartIdx, nMiddleIdx, asc);
            numbers = SplitAndMerge(DEBUG_TRACE, numbers, nMiddleIdx + 1, nEndIdx, asc);

            return Merge(numbers, nStartIdx, nMiddleIdx, nEndIdx, asc);
        }

        private int[] Merge(int[] numbers, int nStartIdx, int nMiddleIdx, int nEndIdx, bool asc)
        {
            int[] left = new int[nMiddleIdx - nStartIdx + 1];       // array from nStartIdx to nMiddleIdx
            int[] right = new int[nEndIdx - nMiddleIdx];            // array from nMiddleIdx + 1 to nEndIdx

            int j = nStartIdx;
            for (int i = 0; i < left.Length; i++, j++)
                left[i] = numbers[j];

            j = nMiddleIdx + 1;
            for (int i = 0; i < right.Length; i++, j ++)
                right[i] = numbers[j];

            int l = 0;
            int r = 0;

            for (int i = nStartIdx; i <= nEndIdx; i ++)
            {
                if (r == right.Length ||                                    // all items in right were placed in numbers allready
                    (l < left.Length && Compare(left[l], right[r], asc)))   // there are still items in left, and left item is less (asc = true) or bigger (asc = false) than the right item
                {
                    numbers[i] = left[l];
                    l ++;
                }
                else
                {
                    numbers[i] = right[r];
                    r ++;
                }
            }

            return numbers;
        }
        #endregion

        #region Dump Methods
        private void DUMP(int[] numbers, int nStartIdx, int nEndIdx, DebugTraceDelegate DEBUG_TRACE, bool bWithClear)
        {
            DEBUG_TRACE(numbers, string.Format("sIdx = {0}, mIdx = {1}, eIdx = {2}", nStartIdx, (nStartIdx + nEndIdx) / 2, nEndIdx), bWithClear);
        }
        #endregion
    }
}
